package com.salim.leetcode.$42;

import lombok.extern.slf4j.Slf4j;

@Slf4j
public class TrappingRainWater {
    //超时
//    public int trap(int[] height) {
//        int result = 0;
//        result = loop(height,result,1);
//        return result;
//    }
//
//    public int loop(int[] height,int result,int base){
//        int blankLeft = -1;
//        int blankRight = -1;
//        int index = 0;
//        while (blankLeft==-1 && index<height.length){
//            if(height[index]-base>=0){
//                blankLeft = index;
//                break;
//            }
//            index++;
//        }
//        index = height.length-1;
//        while (blankRight==-1 && index>0){
//            if(height[index]-base>=0){
//                blankRight = index;
//                break;
//            }
//            index--;
//        }
//        if(blankLeft==blankRight){
//            return result;
//        }
//        for(int i=blankLeft+1;i<blankRight;i++){
//            if(height[i]<base){
//                result+=1;
//            }
//        }
//        return loop(height,result,++base);
//    }

    public int trap(int[] height) {
        if(height.length<=1){
            return 0;
        }
        int result = 0;
        for(int i=1;i<height.length-1;i++){
            int leftHeight = height[i-1];
            if(leftHeight==0){
                continue;
            }
            if(leftHeight<=height[i]){
                continue;
            }
            int rightIndex = -1;
            int total = 0;
            int nextHeightIndex = i;
            int nextHeightTotal = 0;
            for(int j=i;j<height.length;j++){
                if(height[j]<leftHeight){
                    if(height[nextHeightIndex]<height[j]){
                        nextHeightIndex = j;
                        nextHeightTotal = total;
                    }
                    total+=height[j];
                    continue;
                }else{
                    rightIndex = j;
                    break;
                }
            }

            if(rightIndex==-1){
                if(nextHeightIndex!=i){
                    rightIndex = nextHeightIndex;
                    total = nextHeightTotal;
                }else{
                    continue;
                }
            }

            //计算
            if(leftHeight>=height[rightIndex]){
                result+= height[rightIndex]*(rightIndex-i) - total;
            }else{
                result+= leftHeight*(rightIndex-i) - total;
            }
            i = rightIndex;
        }
        return result;
    }

    public static void main(String[] args) {
        TrappingRainWater t = new TrappingRainWater();
        log.info("TrappingRainWater输出结果1：{}", t.trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
        log.info("TrappingRainWater输出结果2：{}", t.trap(new int[]{4,2,3}));
//        log.info("FirstMissingPositive输出结果3：{}", t.trap(new int[]{3,4,-1,1}));
//        log.info("FirstMissingPositive输出结果4：{}", t.trap(new int[]{7,8,9,11,12}));
    }

}
